Computer Programming Activity Selection Problem, Fractional Knapsack Problem গাইড ও নোট

Activity Selection Problem এবং Fractional Knapsack Problem দুটি গুরুত্বপূর্ণ গ্রীড-ভিত্তিক অপটিমাইজেশন সমস্যা। এই সমস্যা গুলি প্রায়ই গ্রীড বা কন্টিনিউয়াস ডেটা স্ট্রাকচারের মধ্যে সমাধান করা হয় এবং তাদের মধ্যে বেশ কিছু অ্যালগরিদম ব্যবহার করা হয়।

১. Activity Selection Problem

Activity Selection Problem হল একটি ক্লাসিকাল অপটিমাইজেশন সমস্যা যেখানে আপনাকে কিছু কর্মকাণ্ড (activities) দেওয়া হয় এবং আপনার কাজ হল, আপনি কতগুলো কর্মকাণ্ড একসাথে সম্পন্ন করতে পারেন এমনভাবে বেছে নেওয়া, যাতে তাদের মধ্যে সময়ের মধ্যে কোনও সম্পর্ক না থাকে (অর্থাৎ, একটির সময় অন্যটির সাথে ওভারল্যাপ না করে)।

Problem Description:

• আপনাকে বিভিন্ন কর্মকাণ্ডের একটি তালিকা দেওয়া হয় যেখানে প্রতিটি কর্মকাণ্ডের একটি স্টার্ট টাইম এবং একটি এন্ড টাইম আছে।
• আপনার কাজ হল এমন কর্মকাণ্ড নির্বাচন করা, যাতে তাদের মধ্যে কোনও সময়ের চূড়ান্ত অঙ্ক না থাকে এবং যত বেশি সম্ভব কর্মকাণ্ড নির্বাচিত হয়।

Solution Approach:

এই সমস্যা সমাধানের জন্য Greedy Algorithm ব্যবহার করা হয়। অ্যালগরিদমটি নিম্নলিখিত ধাপে কাজ করে:

1. Activities Sort: প্রথমে সমস্ত কর্মকাণ্ডের এন্ড টাইম অনুযায়ী সাজানো হয়।
2. প্রথম কর্মকাণ্ডটি নির্বাচন করুন এবং তারপর একে একে পরবর্তী কর্মকাণ্ডগুলো চেক করুন।
3. যদি কোনো কর্মকাণ্ডের স্টার্ট টাইম পূর্ববর্তী নির্বাচিত কর্মকাণ্ডের এন্ড টাইম এর পরে থাকে, তবে সেটি নির্বাচন করুন।

Time Complexity:

• Sorting: O(n log n)
• Selection: O(n)
• Total Time Complexity: O(n log n)

সি প্রোগ্রামে Activity Selection Problem এর ইমপ্লিমেন্টেশন:

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int start;
    int end;
} Activity;

int compare(const void *a, const void *b) {
    return ((Activity *)a)->end - ((Activity *)b)->end;
}

void selectActivities(Activity activities[], int n) {
    // Sort activities by end time
    qsort(activities, n, sizeof(Activity), compare);

    printf("Selected activities are:\n");
    
    // The first activity is always selected
    int lastSelected = 0;
    printf("Activity %d: [%d, %d]\n", 1, activities[lastSelected].start, activities[lastSelected].end);
    
    // Check remaining activities
    for (int i = 1; i < n; i++) {
        if (activities[i].start >= activities[lastSelected].end) {
            lastSelected = i;
            printf("Activity %d: [%d, %d]\n", i + 1, activities[lastSelected].start, activities[lastSelected].end);
        }
    }
}

int main() {
    Activity activities[] = {{1, 3}, {2, 5}, {4, 7}, {6, 8}, {5, 9}};
    int n = sizeof(activities) / sizeof(activities[0]);
    
    selectActivities(activities, n);

    return 0;
}

২. Fractional Knapsack Problem

Fractional Knapsack Problem একটি অপটিমাইজেশন সমস্যা যেখানে একটি স্লটের মধ্যে ডেটা সংরক্ষণ করতে আপনাকে কিছু আইটেম দেওয়া হয় এবং তাদের মধ্যে সর্বোচ্চ মূল্য (value) অর্জন করার জন্য, আপনি কিছু আইটেম সম্পূর্ণ বা আংশিকভাবে নিতে পারেন। এর মানে, আপনি আইটেমগুলোকে টুকরো টুকরো করে নিতে পারবেন (Fractional), যা 0/1 Knapsack Problem থেকে পৃথক।

Problem Description:

• আপনি একটি ন্যূনতম ক্ষমতা সম্পন্ন ব্যাগের মধ্যে বিভিন্ন আইটেম নির্বাচন করবেন।
• প্রতিটি আইটেমের একটি ওজন (weight) এবং একটি মূল্য (value) থাকবে।
• আপনি যে কোন আইটেমের একাধিক অংশ নিতে পারবেন, অর্থাৎ Fractional Knapsack।
• আপনার লক্ষ্য হলো, ব্যাগের মধ্যে সর্বোচ্চ মূল্য (value) সন্নিবেশ করা।

Solution Approach:

এই সমস্যাটি সমাধান করার জন্য Greedy Algorithm ব্যবহার করা হয়, যেখানে প্রথমে আইটেমগুলির মূল্য প্রতি ইউনিট ওজনের জন্য (value/weight) অনুপাত হিসাব করা হয়। এরপর আইটেমগুলোকে এই অনুপাত অনুযায়ী সাজানো হয়, এবং তাদের একে একে ব্যাগে সন্নিবেশ করা হয় যতক্ষণ না ব্যাগ পূর্ণ হয়।

Time Complexity:

• Sorting: O(n log n)
• Selection: O(n)
• Total Time Complexity: O(n log n)

সি প্রোগ্রামে Fractional Knapsack Problem এর ইমপ্লিমেন্টেশন:

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int weight;
    int value;
    double ratio;
} Item;

int compare(const void *a, const void *b) {
    return ((Item *)b)->ratio - ((Item *)a)->ratio;
}

double fractionalKnapsack(Item items[], int n, int capacity) {
    // Sort items by value/weight ratio
    qsort(items, n, sizeof(Item), compare);

    double totalValue = 0.0;
    for (int i = 0; i < n; i++) {
        if (items[i].weight <= capacity) {
            // Take the full item
            totalValue += items[i].value;
            capacity -= items[i].weight;
        } else {
            // Take the fractional part of the item
            totalValue += items[i].value * ((double) capacity / items[i].weight);
            break;
        }
    }

    return totalValue;
}

int main() {
    Item items[] = {{10, 60, 0}, {20, 100, 0}, {30, 120, 0}};
    int n = sizeof(items) / sizeof(items[0]);
    int capacity = 50;
    
    // Calculate value per weight ratio for each item
    for (int i = 0; i < n; i++) {
        items[i].ratio = (double) items[i].value / items[i].weight;
    }
    
    double maxValue = fractionalKnapsack(items, n, capacity);
    printf("Maximum value in Knapsack = %.2f\n", maxValue);

    return 0;
}

Comparison Between Activity Selection and Fractional Knapsack Problem

সারসংক্ষেপ

• Activity Selection Problem একটি Greedy Algorithm ব্যবহার করে সমাধান করা হয়, যেখানে একাধিক কর্মকাণ্ডের মধ্যে যেগুলি একে অপরের সাথে অতিক্রম করবে না, তা নির্বাচন করা হয়। এর Time Complexity O(n log n) হয়।
• Fractional Knapsack Problem একটি Greedy Algorithm ব্যবহার করে সমাধান করা হয়, যেখানে আইটেমের মূল্য/ওজন অনুপাত অনুসারে আইটেমগুলি বাছাই করা হয়। এটি আংশিকভাবে আইটেম গ্রহণ করতে সক্ষম, যার ফলে এটি 0/1 Knapsack Problem থেকে আলাদা।

উভয় সমস্যা অপটিমাইজেশন পদ্ধতি ব্যবহার করে, তবে তাদের আবেদন ক্ষেত্র এবং অ্যালগরিদমের ধরণ ভিন্ন।